//给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语
//的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
//
//
//
// 示例 1:
//
//
//输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
//输出: 16
//解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。
//
// 示例 2:
//
//
//输入: words = ["a","ab","abc","d","cd","bcd","abcd"]
//输出: 4
//解释: 这两个单词为 "ab", "cd"。
//
// 示例 3:
//
//
//输入: words = ["a","aa","aaa","aaaa"]
//输出: 0
//解释: 不存在这样的两个单词。
//
//
//
//
// 提示：
//
//
// 2 <= words.length <= 1000
// 1 <= words[i].length <= 1000
// words[i] 仅包含小写字母
//
//
//
//
//
// 注意：本题与主站 318 题相同：https://leetcode-cn.com/problems/maximum-product-of-word-
//lengths/
//
// Related Topics 位运算 数组 字符串 👍 146 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
//? 暴力
function maxProduct(words: string[]): number {
    /**
     * @param {string[]} words
     * @return {number}
     */
    const l = words.length;
    let res = 0;
    for(let i = 0;i < l;i++){
        for(let j = i + 1;j < l;j++){
            // 判断两个单词如果没有出现重复字符，则求最大的单词乘积
            if(!hasSameLetter(words[i],words[j])){
                res = Math.max(words[i].length * words[j].length,res);
            }
        }
    }
    return res
};
function hasSameLetter(wordA,wordB){
    for(const letter of wordA){
        if(wordB.indexOf(letter) !== -1){
            return true;
        }
    }
    return false;
};
//leetcode submit region end(Prohibit modification and deletion)
//? 位运算优化比较函数
function maxProduct2(words: string[]): number {
    function hasSameLetter(wordA,wordB){
        let x = 0,y = 0;
        for(const letter of wordA){
            //? 字符串的charCodeAt方法可以得到字母的ascii码值
            //? 1 << 将1左移两字字母ASCII差值的位数
            //? 在26位数字上模拟存放a-z 有就是1 所以这里使用了按位或 |=
            x |= 1 << (letter.charCodeAt() - "a".charCodeAt(0));
        }
        for(const letter of wordB){
            //? 字符串的charCodeAt方法可以得到字母的ascii码值
            y |= 1 << (letter.charCodeAt() - "a".charCodeAt(0));
        }
        //? 按位操作符优先级低因此需要加括号,按位与判断是否重复
        return (x & y) !== 0;
    }

    /**
     * @param {string[]} words
     * @return {number}
     */
    const l = words.length;
    let res = 0;
    for(let i = 0;i < l;i++){
        for(let j = i + 1;j < l;j++){
            //? 判断两个单词如果没有出现重复字符，则求最大的单词乘积
            if(!hasSameLetter(words[i],words[j])){
                res = Math.max(words[i].length * words[j].length,res);
            }
        }
    }
    return res
};
//? 再优化双循环
function maxProduct3(words: string[]): number {
    /**
     * @param {string[]} words
     * @return {number}
     */
    let map = new Map(),
        n = words.length,
        res = 0;
    const asciiA = "a".charCodeAt(0);
    for(let i = 0;i < n;i++){
        let temp = 0;
        for(const c of words[i]){
            temp |= 1 << (c.charCodeAt(0) - asciiA);
        }
        // 根据temp来设置单词的长度
        if(map.has(temp)){
            // 设置单词长度的最大值
            map.set(temp,Math.max(words[i].length,map.get(temp)));
        }else{
            map.set(temp,words[i].length);
        }
    }
    for(const keyA of map.keys()){
        for(const keyB of map.keys()){
            // 按位与操作为0，则代表单词字符不重复
            if((keyA & keyB) === 0){
                res = Math.max(res,map.get(keyA) * map.get(keyB));
            }
        }
    }
    return res;

};
//leetcode submit region end(Prohibit modification and deletion)
